INTRODUCTION

In this case study, we’ll perform customer segmentation using k-means, a clustering algorithm

Clustering

Clustering is an unsupervised machine learning task that automatically divides the data into clusters or groupings of similar items. It does this without having been told what the groups should look like ahead of time. As we may not even know what we’re looking for, clustering is used for knowledge discovery rather than prediction. It provides an insight into the natural groupings found within data.

K-means algorithm

The k-means is the widest used unsupervised machine learning algorithm. It basically tries to minimize the distance of the points in a cluster with their centroid. This results in the creation of groups/segments with different characteristics (as different as possible)

Business Benefits

There are a lot of benefits when using segmentation in a business context. In particular when a business develops a successful customer segmentation, that means that instead of treating all customers the same, now each customer is assigned to a cluster. So the business can apply different strategies to each segment/cluster, which contribute to improving/optimizing e.g.:

  • Customer retention
  • Customer satisfaction
  • Sales revenue
  • Product pricing

Our problem

Our company has 368 B2B customers and we need i) Create a centralized pricing policy regarding different segments of customers & ii) Improve our customer satisfaction & retention through targeted marketing campaigns.

The stakeholders decided to develop a customer segmentation to:

  • Apply different discount policies on each segment and optimize revenue
  • Design different marketing campaigns on each segment to optimize customer retention & satisfaction

All the data used for the analysis are anonymized.

Initial ETL & Feature engineering

This is a very important step in every data science project, especially when performing clustering.

We have to work along with the stakeholders, as they will help us identify the important customer features and how we can obtain these (via ERP, CRM systems, Surveys e.t.c). In this step, you may spend most of your time during similar projects, as we need meaningful & important features to perform a successful segmentation.

Import libraries

At first we are loading all libraries.


library(tidyverse)
library(ggthemes)
library(DT)
Registered S3 method overwritten by 'htmlwidgets':
  method           from         
  print.htmlwidget tools:rstudio
library(d3heatmap)
library(plotly)
Registered S3 method overwritten by 'data.table':
  method           from
  print.data.table     

Attaching package: ‘plotly’

The following object is masked from ‘package:ggplot2’:

    last_plot

The following object is masked from ‘package:stats’:

    filter

The following object is masked from ‘package:graphics’:

    layout
library(ggfortify)

# Set the black & white theme for all plots
theme_set(theme_bw())

# Use it to prevent scientific notation
options(scipen = 999)

Load dataset

We’ll use the final dataset, which is the result of the initial ETL & feature engineering step.

We use the read_csv() function (from readr library) to read the csv file in R.

customers <- read_csv(file = "data/customers.csv")
Parsed with column specification:
cols(
  customer = col_character(),
  area = col_character(),
  certifications = col_double(),
  last_year_revenue = col_double(),
  new_products_prop = col_double(),
  new_products_revenue = col_double(),
  active_quarters = col_double(),
  median_quarterly_dso = col_double(),
  median_quarterly_balance = col_double(),
  total_revenue = col_double(),
  product_cat_A_revenue = col_double(),
  product_cat_B_revenue = col_double(),
  product_cat_C_revenue = col_double(),
  product_cat_D_revenue = col_double()
)

EXPLORATORY ANALYSIS

Inspect the dataset

customers %>% glimpse()
Rows: 368
Columns: 14
$ customer                 <chr> "Customer_1", "Customer_2", "Customer_3", "Customer_4", "Customer_5", "Cus…
$ area                     <chr> "Area_C", "Area_A", "Area_A", "Area_C", "Area_A", "Area_C", "Area_C", "Are…
$ certifications           <dbl> 0, 0, 0, 1, 1, 0, 0, 0, 0, 3, 0, 0, 0, 6, 0, 9, 0, 1, 0, 5, 0, 1, 0, 0, 9,…
$ last_year_revenue        <dbl> 14735.25, 1273.50, 8493.00, 8556.75, 18706.50, 9755.25, 446.25, 13469.25, …
$ new_products_prop        <dbl> 33.66, 0.00, 27.90, 5.94, 3.51, 5.58, 15.84, 0.00, 18.36, 14.85, 0.00, 56.…
$ new_products_revenue     <dbl> 5511.00, 0.00, 2636.25, 566.25, 721.50, 600.00, 78.75, 0.00, 195.75, 3820.…
$ active_quarters          <dbl> 3, 2, 7, 54, 53, 3, 15, 3, 1, 57, 37, 4, 1, 38, 12, 19, 38, 54, 2, 4, 2, 3…
$ median_quarterly_dso     <dbl> 82, 112, 123, 118, 82, 77, 82, 0, 0, 117, 82, 0, 82, 82, 0, 94, 108, 93, 0…
$ median_quarterly_balance <dbl> 1262.25, 594.15, 6261.10, 4063.85, 5218.15, 2476.90, 505.75, 10200.00, 0.0…
$ total_revenue            <dbl> 2736.00, 735.00, 20482.50, 147867.75, 171960.00, 2983.50, 14721.75, 16469.…
$ product_cat_A_revenue    <dbl> 7825.2375, 1273.8750, 616.1850, 4877.4375, 7594.0425, 9155.3850, 0.0000, 1…
$ product_cat_B_revenue    <dbl> 5071.500, 0.000, 0.000, 225.000, 568.875, 0.000, 78.750, 0.000, 195.420, 2…
$ product_cat_C_revenue    <dbl> 1170.000, 0.000, 0.000, 912.000, 2283.750, 0.000, 0.000, 0.000, 0.000, 226…
$ product_cat_D_revenue    <dbl> 369.000, 0.000, 7756.642, 1365.007, 3317.393, 0.000, 367.500, 262.500, 0.0…

All variables are anonymized.

  • customer | The customer name
  • area | The customer area
  • certifications | The number of certifications each customer’s employees hold
  • last_year_revenue | Last year’s total revenue of each customer
  • new_products_prop | The proportion of last year’s revenue generated by each customer with new products vs total revenue
  • new_products_revenue | Last year’s revenue of each customer generated with new products
  • active_quarters | The total number of quarters that this customer was active (at least 1 transaction during an active quarter)
  • median_quarterly_dso | The median quarterly DSO of each customer (Days sales outstanding - measure of the average number of days that it takes a company to collect payment after a sale has been made)
  • median_quarterly_balance | The median quarterly balance of each customer (amount of money customer owes to the company at the end of the quarter)
  • total_revenue | The total revenue each customer generated (historical revenue)
  • product_cat_A_revenue | Last year’s revenue of each customer generated by product category A
  • product_cat_B_revenue | Last year’s revenue of each customer generated by product category B
  • product_cat_C_revenue | Last year’s revenue of each customer generated by product category C
  • product_cat_D_revenue | Last year’s revenue of each customer generated by product category D

Check for missing values

It’s very important to check for missing data before our analysis. Especially when we planning to perform clustering, because k-means algorithm can’t handle missing data.

We haven’t got any missing values so we can proceed.

Continuous variables distribution

K-means algorithm can be applied only in continuous variables. So all the variables that we’re using are continuous. Below we check the distribution of each variable

We can see that most of our variables, especially currency-related variables, have a skewness towards large values. It would be a good idea to use a logarithmic scale. In any case, prior to apply clustering we need to scale our variables, so it is a good idea to create some plots using logarithmic scale.

customers %>% 
  select(-customer, -area) %>%  
  gather(key = "Variable", value = "Value") %>%
  ggplot(aes(log(Value))) +
  geom_histogram(bins = 20) +
  facet_wrap(~ Variable, scales = "free") +
  labs(
    title = "Continuous variables histograms with log values",
    x = ""
  ) 

A lot of the log-transformed variables (almost all revenue-related vars) are close to a normal distribution (Log-normal).

Correlogram

It is a chart that presents correlation between the dataset variables.

corrplot(cor(select(customers, -exclude)), type="upper", order="hclust")
Note: Using an external vector in selections is ambiguous.
ℹ Use `all_of(exclude)` instead of `exclude` to silence this message.
ℹ See <https://tidyselect.r-lib.org/reference/faq-external-vector.html>.
This message is displayed once per session.

We can see that there are some strong correlations between the variables. Especially between all currency-related variables. It seems that almost all currency variables are following the same pattern.

Joy plot

Essentially presents overlapping area charts, which make it easy to compare all the distributions

select(customers, -exclude) %>% 
  mutate_all(scale) %>% 
  gather(key = "variable", value = "value") %>% 
  mutate(value = scale(value)) %>% 
  ggplot(aes(x = value,
             y = variable, fill = ..x..)) +
  ggridges::geom_density_ridges_gradient(rel_min_height = 0.0) +
  viridis::scale_fill_viridis(name = "") +
  ggridges::theme_ridges(font_size = 13, grid = TRUE) +
  theme(axis.title.y = element_blank(),
        axis.title.x = element_blank(),
        axis.text.x = element_text(size = 12),
        text = element_text(family = "mono")) +
  scale_x_continuous(limits = c(-2, 2))+
  labs(title = 'Density plots of variables',
       subtitle = 'All values are scaled')
attributes are not identical across measure variables;
they will be dropped

Here we can see again that the distribution of all revenue-related variables are similar.

MODELLING

At first we’ll discover the optimal number of clusters for our dataset. There are two techniques for that, elbow plot & silhouette plot.

Determining optimal number of clusters with elbow plot

Plot of total within cluster sum of squares (the sum of euclidean distances between each observation and the centroid corresponding to the cluster to which the observation is assigned)

The idea here is that we stop adding new segments when the additional information (increase on total within sum of squares) is not significant. In this case 4 & 5 clusters seems OK.

Finally we choose to perform the segmentation with 5 segments because:

  1. it is among the optimal number of segments &
  2. satisfies our business needs.

Build the model with k = 5

model_customers
K-means clustering with 5 clusters of sizes 87, 27, 5, 106, 143

Cluster means:
  certifications last_year_revenue new_products_prop new_products_revenue active_quarters
1    -0.24205640        -0.2151471         1.4021594          -0.05284781      -0.5972864
2     2.15836578         1.4977622         0.1062848           1.39054867       0.7585746
3     3.11953902         6.7245088         0.1467196           6.48816313       1.1675964
4     0.03982787        -0.0920378        -0.1739955          -0.14312797       1.0623485
5    -0.39885607        -0.3187994        -0.7492841          -0.35116297      -0.6081435
  median_quarterly_dso median_quarterly_balance total_revenue product_cat_A_revenue product_cat_B_revenue
1           -0.2274370              -0.27283231   -0.33720357            -0.2438423           -0.07061636
2            0.7564557               1.77153804    1.56472299             1.6544661            1.58426684
3            0.9423862               6.06299794    6.17201374             6.1651859            5.91217991
4            0.5955087              -0.04405098    0.08484561            -0.0879380           -0.13168010
5           -0.4788331              -0.34783708   -0.36898262            -0.3144112           -0.36527545
  product_cat_C_revenue product_cat_D_revenue
1           -0.28371813           -0.19453927
2            1.47054403            1.13789701
3            5.71348767            6.69482156
4           -0.01175898           -0.08857925
5           -0.29609929           -0.26491615

Clustering vector:
  [1] 1 5 1 4 4 5 5 5 5 4 4 1 5 4 5 2 4 4 5 1 5 4 1 5 3 1 5 1 1 4 2 2 4 4 5 4 1 5 4 5 3 1 1 5 4 5 5 2 1 4 5 1
 [53] 1 5 5 5 1 1 1 4 5 4 4 4 5 2 5 1 5 5 4 5 5 5 1 1 5 1 1 4 1 1 2 1 5 5 1 1 5 5 1 5 2 1 2 4 4 4 5 1 1 1 5 5
[105] 2 1 1 2 5 5 1 1 4 1 4 4 1 4 5 5 1 4 5 5 5 5 5 1 5 3 4 2 4 5 4 5 4 5 5 2 5 3 1 4 5 4 4 2 5 4 1 2 1 5 5 1
[157] 1 5 1 4 4 4 4 5 4 5 5 5 1 4 5 4 5 5 5 1 5 5 4 4 5 5 5 5 5 4 4 1 5 5 5 4 5 5 4 4 4 5 1 5 2 1 4 5 5 5 4 4
[209] 4 5 4 5 4 4 5 4 5 5 2 1 5 1 2 5 5 5 4 5 4 5 4 5 4 5 1 4 1 1 1 1 5 4 4 5 5 1 4 4 2 5 5 5 2 2 5 4 4 4 4 4
[261] 4 5 5 2 4 5 5 1 4 4 5 5 5 4 4 5 4 1 5 5 4 3 1 4 4 1 5 1 2 1 2 5 5 5 4 5 4 4 4 2 1 4 5 4 1 5 5 4 2 1 5 5
[313] 5 1 4 4 5 1 4 2 1 1 1 5 5 5 4 5 1 1 1 5 4 1 5 2 1 4 1 1 4 1 4 5 1 5 5 4 5 5 4 4 4 1 5 1 4 5 5 4 1 5 1 4
[365] 1 5 5 5

Within cluster sum of squares by cluster:
[1] 191.4711 354.9338 222.1625 489.0372 137.8794
 (between_SS / total_SS =  68.3 %)

Available components:

[1] "cluster"      "centers"      "totss"        "withinss"     "tot.withinss" "betweenss"    "size"        
[8] "iter"         "ifault"      

Heatmap of cluster centers

This is an easy way to check the differences & similarities of all segments. The center of the cluster is the average of all points (elements) that belong to that cluster. All values are scaled

The more green - the higher the value.

  • Segment 3 containing just 5 customers. These are our “top” customers. They tend to generate way more revenue, have a lot of certifications, purchase quite a big proportion of new products and have a high DSO

  • Segment 2 contains 27 customers. They are “close to the top” customers as they tend to generate high revenue, maintain a high number of certifications, purchase quite a big proportion of new products and have a high DSO

  • Segment 4 contains 106 customers. They are the “average” customers as they tend to generate average revenues, have a small number of certifications, purchase an average proportion of new products and have an average DSO

  • Segment 1 contains 87 customers. They are the “promising” customers as they tend to generate a relatively low revenue, have a small number of certifications, but they purchase a very high proportion of new products and have a small DSO

  • Segment 5 contains 143 customers. They are the “under-performing” customers as they tend to generate a very low revenue, have a very small number of certifications, purchase a very low proportion of new products and have an small DSO

Table of variables

Below there is a table with information about all clusters (with all variables)

# Calculate the mean for each category
segment_customers %>% 
  group_by(cluster) %>% 
  add_tally() %>% 
  summarise_each(funs(round(mean(.),2))) %>% 
  select(1, "n", everything()) %>% 
  arrange(-last_year_revenue) %>% 
  datatable(filter = 'top', options = list(pageLength = 5, autoWidth = TRUE, dom = 'pt'))
`summarise_each_()` is deprecated as of dplyr 0.7.0.
Please use `across()` instead.
This warning is displayed once every 8 hours.
Call `lifecycle::last_warnings()` to see where this warning was generated.

PCA (Principal components analysis)

It is a dimensionality reduction algorithm, that allows you to summarize the information content in large datasets by means of a smaller set of features that can be more easily visualized and analyzed. It will assist us in segmentation visualization (Biplot).

  • It will find linear combination of variables to create principal components
  • These Principal components capture the most variation in a dataset and are uncorrelated
summary(pca_customers)
Importance of components:
                          PC1    PC2     PC3     PC4    PC5     PC6     PC7     PC8     PC9    PC10    PC11
Standard deviation     2.7588 1.1009 1.03266 0.79920 0.7421 0.59581 0.48581 0.36453 0.33325 0.24355 0.12546
Proportion of Variance 0.6342 0.1010 0.08887 0.05323 0.0459 0.02958 0.01967 0.01107 0.00925 0.00494 0.00131
Cumulative Proportion  0.6342 0.7352 0.82409 0.87732 0.9232 0.95280 0.97246 0.98354 0.99279 0.99773 0.99905
                          PC12
Standard deviation     0.10701
Proportion of Variance 0.00095
Cumulative Proportion  1.00000

Biplot

This plot shows all the original observations plotted on the first 2 principal components (which contain almost 75% of the original dataset variance). It also shows the original features mapped as vectors.

It shows that there are 3 distinct groups of variables: - active_quarters & median_dso - new_products_prop - All the revenue-related variables

“Business” Biplot



ggplotly(
          pca_customers$x %>%
          as.data.frame() %>%
          mutate(CLIENT = customers$customer,
                 Cluster = as.factor(segment_customers$cluster),
                 revenue = segment_customers$last_year_revenue,
                 newbusiness = segment_customers$new_products_prop,
                 certifications = segment_customers$certifications) %>%
          select(CLIENT, Cluster, PC1, PC2, revenue, newbusiness, certifications) %>%
          ggplot(aes(PC1, PC2, color = Cluster, text = paste(CLIENT, "\n Revenue: ",
                                                             # scales::dollar(revenue, prefix = "€"), 
                                                             revenue, 
                                                             "\n New Prod. Rev.:", newbusiness, "%\nCertifications:",
                                                             certifications,
                                                             sep = "") )) +
          
          stat_ellipse(aes(label = Cluster, group = Cluster), type = "norm", level = 0.70) +
          geom_point()+
          theme_fivethirtyeight() +
          labs(title = "Business Biplot of customers",
               x = "",
               y = "") +
          scale_color_discrete(name = "Segments") +
          theme_hc(),
        
        tooltip = "text")
Ignoring unknown aesthetics: labelplotly.js does not (yet) support horizontal legend items 
You can track progress here: 
https://github.com/plotly/plotly.js/issues/53 
`group_by_()` is deprecated as of dplyr 0.7.0.
Please use `group_by()` instead.
See vignette('programming') for more help
This warning is displayed once every 8 hours.
Call `lifecycle::last_warnings()` to see where this warning was generated.

We can see here how “well” the segments are separated. For example:
- Segment 3 (“top customers”) are well separated from the rest
- Segment 2 (“Close to top customers”) are just next to the top customers. - Segments 1 & 5 are overlapping.

Almost all segments are clearly distinguished.

Customer segmentation table

Reports the segment & details of all customers.

CONCLUSIONS

The chosen “optimal” number of clusters is 5, which is within the business objectives of the company. It is crucial to work with the stakeholders while running the analysis, in order to produce a useful output.

Segments overview

Segment | # customers | Description | Performance evaluation
3 | 5 | “Top” | Very high on all vars 2 | 27 | “Close to top” | High on all vars 4 | 106 | “Average” | Average on all vars
1 | 87 | “Promising” | Very high new products rev. & low on the rest 5 | 143 | “Under-performers”| Low on all vars

Sugestions

  • We show that almost all revenue-related variables are correlated. We could remove some or most of these variables as they don’t really help the segmentation process.

  • In order to improve our segmentation we need more features. We can meet with the stakeholders and work close to them to find or generate some more features.

  • We can try more clustering algorithms, like hierarchical clustering, DBSCAN etc.

LS0tCnRpdGxlOiAiQ1VTVE9NRVIgU0VHTUVOVEFUSU9OIFVTSU5HIENMVVNURVJJTkciCm91dHB1dDogaHRtbF9ub3RlYm9vawotLS0KCgojIElOVFJPRFVDVElPTgoKSW4gdGhpcyBjYXNlIHN0dWR5LCB3ZSdsbCBwZXJmb3JtIGN1c3RvbWVyIHNlZ21lbnRhdGlvbiB1c2luZyBrLW1lYW5zLCBhIApjbHVzdGVyaW5nIGFsZ29yaXRobQoKIVtdKGltYWdlcy9zZWdtZW50YXRpb24ucG5nKQoKIyMgQ2x1c3RlcmluZwpDbHVzdGVyaW5nIGlzIGFuIHVuc3VwZXJ2aXNlZCBtYWNoaW5lIGxlYXJuaW5nIHRhc2sgdGhhdCBhdXRvbWF0aWNhbGx5IGRpdmlkZXMgCnRoZSBkYXRhIGludG8gY2x1c3RlcnMgb3IgZ3JvdXBpbmdzIG9mIHNpbWlsYXIgaXRlbXMuIEl0IGRvZXMgdGhpcyB3aXRob3V0CmhhdmluZyBiZWVuIHRvbGQgd2hhdCB0aGUgZ3JvdXBzIHNob3VsZCBsb29rIGxpa2UgYWhlYWQgb2YgdGltZS4gQXMgd2UgbWF5IG5vdApldmVuIGtub3cgd2hhdCB3ZSdyZSBsb29raW5nIGZvciwgY2x1c3RlcmluZyBpcyB1c2VkIGZvciBrbm93bGVkZ2UgZGlzY292ZXJ5IApyYXRoZXIgdGhhbiBwcmVkaWN0aW9uLiBJdCBwcm92aWRlcyBhbiBpbnNpZ2h0IGludG8gdGhlIG5hdHVyYWwgZ3JvdXBpbmdzIGZvdW5kCndpdGhpbiBkYXRhLgoKIyMgSy1tZWFucyBhbGdvcml0aG0KClRoZSBrLW1lYW5zIGlzIHRoZSB3aWRlc3QgdXNlZCB1bnN1cGVydmlzZWQgbWFjaGluZSBsZWFybmluZyBhbGdvcml0aG0uIEl0IGJhc2ljYWxseSAKdHJpZXMgdG8gbWluaW1pemUgdGhlIGRpc3RhbmNlIG9mIHRoZSBwb2ludHMgaW4gYSBjbHVzdGVyIHdpdGggdGhlaXIgY2VudHJvaWQuIApUaGlzIHJlc3VsdHMgaW4gdGhlIGNyZWF0aW9uIG9mIGdyb3Vwcy9zZWdtZW50cyB3aXRoIGRpZmZlcmVudCBjaGFyYWN0ZXJpc3RpY3MgKGFzIApkaWZmZXJlbnQgYXMgcG9zc2libGUpCgojIyBCdXNpbmVzcyBCZW5lZml0cwoKVGhlcmUgYXJlIGEgbG90IG9mIGJlbmVmaXRzIHdoZW4gdXNpbmcgc2VnbWVudGF0aW9uIGluIGEgYnVzaW5lc3MgY29udGV4dC4gSW4gCnBhcnRpY3VsYXIgd2hlbiBhIGJ1c2luZXNzIGRldmVsb3BzIGEgc3VjY2Vzc2Z1bCBjdXN0b21lciBzZWdtZW50YXRpb24sIHRoYXQgbWVhbnMgdGhhdCBpbnN0ZWFkIApvZiB0cmVhdGluZyBhbGwgY3VzdG9tZXJzIHRoZSBzYW1lLCBub3cgZWFjaCBjdXN0b21lciBpcyBhc3NpZ25lZCB0byBhIGNsdXN0ZXIuIApTbyB0aGUgYnVzaW5lc3MgY2FuIGFwcGx5IGRpZmZlcmVudCBzdHJhdGVnaWVzIHRvIGVhY2ggc2VnbWVudC9jbHVzdGVyLCB3aGljaCAKY29udHJpYnV0ZSB0byBpbXByb3Zpbmcvb3B0aW1pemluZyBlLmcuOgoKLSBDdXN0b21lciByZXRlbnRpb24gIAotIEN1c3RvbWVyIHNhdGlzZmFjdGlvbiAgCi0gU2FsZXMgcmV2ZW51ZSAgCi0gUHJvZHVjdCBwcmljaW5nICAKCgojIyBPdXIgcHJvYmxlbQoKT3VyIGNvbXBhbnkgaGFzIDM2OCBCMkIgY3VzdG9tZXJzIGFuZCB3ZSBuZWVkIGkpIENyZWF0ZSBhIGNlbnRyYWxpemVkIHByaWNpbmcgcG9saWN5IApyZWdhcmRpbmcgZGlmZmVyZW50IHNlZ21lbnRzIG9mIGN1c3RvbWVycyAmIGlpKSBJbXByb3ZlIG91ciBjdXN0b21lciBzYXRpc2ZhY3Rpb24gJiAKcmV0ZW50aW9uIHRocm91Z2ggdGFyZ2V0ZWQgbWFya2V0aW5nIGNhbXBhaWducy4gCgpUaGUgc3Rha2Vob2xkZXJzIGRlY2lkZWQgdG8gZGV2ZWxvcCBhIGN1c3RvbWVyIHNlZ21lbnRhdGlvbiB0bzogCgotIEFwcGx5IGRpZmZlcmVudCBkaXNjb3VudCBwb2xpY2llcyBvbiBlYWNoIHNlZ21lbnQgYW5kIG9wdGltaXplIHJldmVudWUgIAotIERlc2lnbiBkaWZmZXJlbnQgbWFya2V0aW5nIGNhbXBhaWducyBvbiBlYWNoIHNlZ21lbnQgdG8gb3B0aW1pemUgY3VzdG9tZXIgcmV0ZW50aW9uICYgc2F0aXNmYWN0aW9uCgpBbGwgdGhlIGRhdGEgdXNlZCBmb3IgdGhlIGFuYWx5c2lzIGFyZSBhbm9ueW1pemVkLiAKCiMjIEluaXRpYWwgRVRMICYgRmVhdHVyZSBlbmdpbmVlcmluZyAKClRoaXMgaXMgYSB2ZXJ5IGltcG9ydGFudCBzdGVwIGluIGV2ZXJ5IGRhdGEgc2NpZW5jZSBwcm9qZWN0LCBlc3BlY2lhbGx5IHdoZW4gcGVyZm9ybWluZwpjbHVzdGVyaW5nLiAKCldlIGhhdmUgdG8gd29yayBhbG9uZyB3aXRoIHRoZSBzdGFrZWhvbGRlcnMsIGFzIHRoZXkgd2lsbCBoZWxwIHVzIGlkZW50aWZ5CnRoZSBpbXBvcnRhbnQgY3VzdG9tZXIgZmVhdHVyZXMgYW5kIGhvdyB3ZSBjYW4gb2J0YWluIHRoZXNlICh2aWEgRVJQLCBDUk0gc3lzdGVtcywgU3VydmV5cyBlLnQuYykuCkluIHRoaXMgc3RlcCwgeW91IG1heSBzcGVuZCBtb3N0IG9mIHlvdXIgdGltZSBkdXJpbmcgc2ltaWxhciBwcm9qZWN0cywgYXMgd2UgbmVlZCAKbWVhbmluZ2Z1bCAmIGltcG9ydGFudCBmZWF0dXJlcyB0byBwZXJmb3JtIGEgc3VjY2Vzc2Z1bCBzZWdtZW50YXRpb24uCgoKIyMgSW1wb3J0IGxpYnJhcmllcwoKQXQgZmlyc3Qgd2UgYXJlIGxvYWRpbmcgYWxsIGxpYnJhcmllcy4gCgpgYGB7cn0KCmxpYnJhcnkodGlkeXZlcnNlKQpsaWJyYXJ5KGdndGhlbWVzKQpsaWJyYXJ5KERUKQpsaWJyYXJ5KGQzaGVhdG1hcCkKbGlicmFyeShwbG90bHkpCmxpYnJhcnkoZ2dmb3J0aWZ5KQoKIyBTZXQgdGhlIGJsYWNrICYgd2hpdGUgdGhlbWUgZm9yIGFsbCBwbG90cwp0aGVtZV9zZXQodGhlbWVfYncoKSkKCiMgVXNlIGl0IHRvIHByZXZlbnQgc2NpZW50aWZpYyBub3RhdGlvbgpvcHRpb25zKHNjaXBlbiA9IDk5OSkKCmBgYAoKIyMgTG9hZCBkYXRhc2V0IAoKV2UnbGwgdXNlIHRoZSBmaW5hbCBkYXRhc2V0LCB3aGljaCBpcyB0aGUgcmVzdWx0IG9mIHRoZSBpbml0aWFsIEVUTCAmIGZlYXR1cmUgCmVuZ2luZWVyaW5nIHN0ZXAuICAKCldlIHVzZSB0aGUgcmVhZF9jc3YoKSBmdW5jdGlvbiAoZnJvbSByZWFkciBsaWJyYXJ5KSB0byByZWFkIHRoZSBjc3YgZmlsZSBpbiBSLiAKCmBgYHtyfQoKY3VzdG9tZXJzIDwtIHJlYWRfY3N2KGZpbGUgPSAiZGF0YS9jdXN0b21lcnMuY3N2IikKYGBgCgojIEVYUExPUkFUT1JZIEFOQUxZU0lTCgojIyBJbnNwZWN0IHRoZSBkYXRhc2V0IAoKCmBgYHtyfQpjdXN0b21lcnMgJT4lIGdsaW1wc2UoKQoKY3VzdG9tZXJzICU+JSBWaWV3KCkKYGBgCgpBbGwgdmFyaWFibGVzIGFyZSBhbm9ueW1pemVkLiAKCi0gY3VzdG9tZXIgfCBUaGUgY3VzdG9tZXIgbmFtZSAgCi0gYXJlYSB8IFRoZSBjdXN0b21lciBhcmVhICAKLSBjZXJ0aWZpY2F0aW9ucyB8IFRoZSBudW1iZXIgb2YgY2VydGlmaWNhdGlvbnMgZWFjaCBjdXN0b21lcidzIGVtcGxveWVlcyBob2xkICAKLSBsYXN0X3llYXJfcmV2ZW51ZSB8IExhc3QgeWVhcidzIHRvdGFsIHJldmVudWUgb2YgZWFjaCBjdXN0b21lciAgCi0gbmV3X3Byb2R1Y3RzX3Byb3AgfCBUaGUgcHJvcG9ydGlvbiBvZiBsYXN0IHllYXIncyByZXZlbnVlIGdlbmVyYXRlZCBieSBlYWNoIGN1c3RvbWVyIHdpdGggbmV3IHByb2R1Y3RzIHZzIHRvdGFsIHJldmVudWUKLSBuZXdfcHJvZHVjdHNfcmV2ZW51ZSB8IExhc3QgeWVhcidzIHJldmVudWUgb2YgZWFjaCBjdXN0b21lciBnZW5lcmF0ZWQgd2l0aCBuZXcgcHJvZHVjdHMgCi0gYWN0aXZlX3F1YXJ0ZXJzIHwgVGhlIHRvdGFsIG51bWJlciBvZiBxdWFydGVycyB0aGF0IHRoaXMgY3VzdG9tZXIgd2FzIGFjdGl2ZSAoYXQgbGVhc3QgMSB0cmFuc2FjdGlvbiBkdXJpbmcgYW4gYWN0aXZlIHF1YXJ0ZXIpICAKLSBtZWRpYW5fcXVhcnRlcmx5X2RzbyB8IFRoZSBtZWRpYW4gcXVhcnRlcmx5IERTTyBvZiBlYWNoIGN1c3RvbWVyIChEYXlzIHNhbGVzIG91dHN0YW5kaW5nIC0gbWVhc3VyZSBvZiB0aGUgYXZlcmFnZSBudW1iZXIgb2YgZGF5cyB0aGF0IGl0IHRha2VzIGEgY29tcGFueSB0byBjb2xsZWN0IHBheW1lbnQgYWZ0ZXIgYSBzYWxlIGhhcyBiZWVuIG1hZGUpIAotIG1lZGlhbl9xdWFydGVybHlfYmFsYW5jZSB8IFRoZSBtZWRpYW4gcXVhcnRlcmx5IGJhbGFuY2Ugb2YgZWFjaCBjdXN0b21lciAoYW1vdW50IG9mIG1vbmV5IGN1c3RvbWVyIG93ZXMgdG8gdGhlIGNvbXBhbnkgYXQgdGhlIGVuZCBvZiB0aGUgcXVhcnRlcikgIAotIHRvdGFsX3JldmVudWUgfCBUaGUgdG90YWwgcmV2ZW51ZSBlYWNoIGN1c3RvbWVyIGdlbmVyYXRlZCAoaGlzdG9yaWNhbCByZXZlbnVlKSAKLSBwcm9kdWN0X2NhdF9BX3JldmVudWUgfCBMYXN0IHllYXIncyByZXZlbnVlIG9mIGVhY2ggY3VzdG9tZXIgZ2VuZXJhdGVkIGJ5IHByb2R1Y3QgY2F0ZWdvcnkgQSAgICAKLSBwcm9kdWN0X2NhdF9CX3JldmVudWUgfCBMYXN0IHllYXIncyByZXZlbnVlIG9mIGVhY2ggY3VzdG9tZXIgZ2VuZXJhdGVkIGJ5IHByb2R1Y3QgY2F0ZWdvcnkgQiAgIAotIHByb2R1Y3RfY2F0X0NfcmV2ZW51ZSB8IExhc3QgeWVhcidzIHJldmVudWUgb2YgZWFjaCBjdXN0b21lciBnZW5lcmF0ZWQgYnkgcHJvZHVjdCBjYXRlZ29yeSBDICAKLSBwcm9kdWN0X2NhdF9EX3JldmVudWUgfCBMYXN0IHllYXIncyByZXZlbnVlIG9mIGVhY2ggY3VzdG9tZXIgZ2VuZXJhdGVkIGJ5IHByb2R1Y3QgY2F0ZWdvcnkgRCAgCgoKIyMgQ2hlY2sgZm9yIG1pc3NpbmcgdmFsdWVzCgpJdCdzIHZlcnkgaW1wb3J0YW50IHRvIGNoZWNrIGZvciBtaXNzaW5nIGRhdGEgYmVmb3JlIG91ciBhbmFseXNpcy4gRXNwZWNpYWxseSAKd2hlbiB3ZSBwbGFubmluZyB0byBwZXJmb3JtIGNsdXN0ZXJpbmcsIGJlY2F1c2Ugay1tZWFucyBhbGdvcml0aG0gY2FuJ3QgaGFuZGxlCm1pc3NpbmcgZGF0YS4gCgpgYGB7cn0KY3VzdG9tZXJzICU+JQogICAgbWFwX2RmKH4gc3VtKGlzLm5hKC4pKSkgJT4lCiAgICBnYXRoZXIoKSAlPiUKICAgIGFycmFuZ2UoZGVzYyh2YWx1ZSkpCgpgYGAKCldlIGhhdmVuJ3QgZ290IGFueSBtaXNzaW5nIHZhbHVlcyBzbyB3ZSBjYW4gcHJvY2VlZC4gCgojIyBDb250aW51b3VzIHZhcmlhYmxlcyBkaXN0cmlidXRpb24KCkstbWVhbnMgYWxnb3JpdGhtIGNhbiBiZSBhcHBsaWVkIG9ubHkgaW4gY29udGludW91cyB2YXJpYWJsZXMuIFNvIGFsbCB0aGUgdmFyaWFibGVzIAp0aGF0IHdlJ3JlIHVzaW5nIGFyZSBjb250aW51b3VzLiBCZWxvdyB3ZSBjaGVjayB0aGUgZGlzdHJpYnV0aW9uIG9mIGVhY2ggdmFyaWFibGUKCmBgYHtyfQoKY3VzdG9tZXJzICU+JSAKICBzZWxlY3QoLWN1c3RvbWVyLCAtYXJlYSkgJT4lICAKICBnYXRoZXIoa2V5ID0gIlZhcmlhYmxlIiwgdmFsdWUgPSAiVmFsdWUiKSAlPiUKICBnZ3Bsb3QoYWVzKFZhbHVlKSkgKwogIGdlb21faGlzdG9ncmFtKGJpbnMgPSAyMCkgKwogIGZhY2V0X3dyYXAofiBWYXJpYWJsZSwgc2NhbGVzID0gImZyZWUiKSArCiAgbGFicygKICAgIHRpdGxlID0gIkNvbnRpbnVvdXMgdmFyaWFibGVzIGhpc3RvZ3JhbXMiLAogICAgeCA9ICIiCiAgKSAKCgpgYGAKCldlIGNhbiBzZWUgdGhhdCBtb3N0IG9mIG91ciB2YXJpYWJsZXMsIGVzcGVjaWFsbHkgY3VycmVuY3ktcmVsYXRlZCB2YXJpYWJsZXMsIGhhdmUgYSAKc2tld25lc3MgdG93YXJkcyBsYXJnZSB2YWx1ZXMuIEl0IHdvdWxkIGJlIGEgZ29vZCBpZGVhIHRvIHVzZSBhIGxvZ2FyaXRobWljIHNjYWxlLiAKSW4gYW55IGNhc2UsIHByaW9yIHRvIGFwcGx5IGNsdXN0ZXJpbmcgd2UgbmVlZCB0byBzY2FsZSBvdXIgdmFyaWFibGVzLCBzbyBpdCAKaXMgYSBnb29kIGlkZWEgdG8gY3JlYXRlIHNvbWUgcGxvdHMgdXNpbmcgbG9nYXJpdGhtaWMgc2NhbGUuIAoKYGBge3J9CmN1c3RvbWVycyAlPiUgCiAgc2VsZWN0KC1jdXN0b21lciwgLWFyZWEpICU+JSAgCiAgZ2F0aGVyKGtleSA9ICJWYXJpYWJsZSIsIHZhbHVlID0gIlZhbHVlIikgJT4lCiAgZ2dwbG90KGFlcyhsb2coVmFsdWUpKSkgKwogIGdlb21faGlzdG9ncmFtKGJpbnMgPSAyMCkgKwogIGZhY2V0X3dyYXAofiBWYXJpYWJsZSwgc2NhbGVzID0gImZyZWUiKSArCiAgbGFicygKICAgIHRpdGxlID0gIkNvbnRpbnVvdXMgdmFyaWFibGVzIGhpc3RvZ3JhbXMgd2l0aCBsb2cgdmFsdWVzIiwKICAgIHggPSAiIgogICkgCgpgYGAKQSBsb3Qgb2YgdGhlIGxvZy10cmFuc2Zvcm1lZCB2YXJpYWJsZXMgKGFsbW9zdCBhbGwgcmV2ZW51ZS1yZWxhdGVkIHZhcnMpIGFyZSBjbG9zZSB0byBhIG5vcm1hbCBkaXN0cmlidXRpb24gKExvZy1ub3JtYWwpLiAKCiMjIENvcnJlbG9ncmFtIAoKSXQgaXMgYSBjaGFydCB0aGF0IHByZXNlbnRzIGNvcnJlbGF0aW9uIGJldHdlZW4gdGhlIGRhdGFzZXQgdmFyaWFibGVzLiAKCmBgYHtyfQpsaWJyYXJ5KGNvcnJwbG90KQoKZXhjbHVkZSA8LSBjKCJjdXN0b21lciIsICJhcmVhIikKCmNvcnJwbG90KGNvcihzZWxlY3QoY3VzdG9tZXJzLCAtZXhjbHVkZSkpLCB0eXBlPSJ1cHBlciIsIG9yZGVyPSJoY2x1c3QiKQoKYGBgCgpXZSBjYW4gc2VlIHRoYXQgdGhlcmUgYXJlIHNvbWUgc3Ryb25nIGNvcnJlbGF0aW9ucyBiZXR3ZWVuIHRoZSB2YXJpYWJsZXMuIEVzcGVjaWFsbHkKYmV0d2VlbiBhbGwgY3VycmVuY3ktcmVsYXRlZCB2YXJpYWJsZXMuIEl0IHNlZW1zIHRoYXQgYWxtb3N0IGFsbCBjdXJyZW5jeSAKdmFyaWFibGVzIGFyZSBmb2xsb3dpbmcgdGhlIHNhbWUgcGF0dGVybi4gCgojIyBKb3kgcGxvdAoKRXNzZW50aWFsbHkgcHJlc2VudHMgb3ZlcmxhcHBpbmcgYXJlYSBjaGFydHMsIHdoaWNoIG1ha2UgaXQgZWFzeSB0byBjb21wYXJlIGFsbAp0aGUgZGlzdHJpYnV0aW9ucwoKYGBge3J9CgpzZWxlY3QoY3VzdG9tZXJzLCAtZXhjbHVkZSkgJT4lIAogIG11dGF0ZV9hbGwoc2NhbGUpICU+JSAKICBnYXRoZXIoa2V5ID0gInZhcmlhYmxlIiwgdmFsdWUgPSAidmFsdWUiKSAlPiUgCiAgbXV0YXRlKHZhbHVlID0gc2NhbGUodmFsdWUpKSAlPiUgCiAgZ2dwbG90KGFlcyh4ID0gdmFsdWUsCiAgICAgICAgICAgICB5ID0gdmFyaWFibGUsIGZpbGwgPSAuLnguLikpICsKICBnZ3JpZGdlczo6Z2VvbV9kZW5zaXR5X3JpZGdlc19ncmFkaWVudChyZWxfbWluX2hlaWdodCA9IDAuMCkgKwogIHZpcmlkaXM6OnNjYWxlX2ZpbGxfdmlyaWRpcyhuYW1lID0gIiIpICsKICBnZ3JpZGdlczo6dGhlbWVfcmlkZ2VzKGZvbnRfc2l6ZSA9IDEzLCBncmlkID0gVFJVRSkgKwogIHRoZW1lKGF4aXMudGl0bGUueSA9IGVsZW1lbnRfYmxhbmsoKSwKICAgICAgICBheGlzLnRpdGxlLnggPSBlbGVtZW50X2JsYW5rKCksCiAgICAgICAgYXhpcy50ZXh0LnggPSBlbGVtZW50X3RleHQoc2l6ZSA9IDEyKSwKICAgICAgICB0ZXh0ID0gZWxlbWVudF90ZXh0KGZhbWlseSA9ICJtb25vIikpICsKICBzY2FsZV94X2NvbnRpbnVvdXMobGltaXRzID0gYygtMiwgMikpKwogIGxhYnModGl0bGUgPSAnRGVuc2l0eSBwbG90cyBvZiB2YXJpYWJsZXMnLAogICAgICAgc3VidGl0bGUgPSAnQWxsIHZhbHVlcyBhcmUgc2NhbGVkJykKYGBgCgpIZXJlIHdlIGNhbiBzZWUgYWdhaW4gdGhhdCB0aGUgZGlzdHJpYnV0aW9uIG9mIGFsbCByZXZlbnVlLXJlbGF0ZWQgdmFyaWFibGVzIGFyZSAKc2ltaWxhci4gCgoKIyBNT0RFTExJTkcKCkF0IGZpcnN0IHdlJ2xsIGRpc2NvdmVyIHRoZSBvcHRpbWFsIG51bWJlciBvZiBjbHVzdGVycyBmb3Igb3VyIGRhdGFzZXQuIFRoZXJlIGFyZQp0d28gdGVjaG5pcXVlcyBmb3IgdGhhdCwgZWxib3cgcGxvdCAmIHNpbGhvdWV0dGUgcGxvdC4KCiMjIERldGVybWluaW5nIG9wdGltYWwgbnVtYmVyIG9mIGNsdXN0ZXJzIHdpdGggZWxib3cgcGxvdAoKUGxvdCBvZiB0b3RhbCB3aXRoaW4gY2x1c3RlciBzdW0gb2Ygc3F1YXJlcyAodGhlIHN1bSBvZiBldWNsaWRlYW4gZGlzdGFuY2VzIApiZXR3ZWVuIGVhY2ggb2JzZXJ2YXRpb24gYW5kIHRoZSBjZW50cm9pZCBjb3JyZXNwb25kaW5nIHRvIHRoZSBjbHVzdGVyIHRvIHdoaWNoCnRoZSBvYnNlcnZhdGlvbiBpcyBhc3NpZ25lZCkKCmBgYHtyIGVjaG89RkFMU0UsIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0UsIHBhZ2VkLnByaW50PUZBTFNFfQpsaWJyYXJ5KHB1cnJyKQpsaWJyYXJ5KGNsdXN0ZXIpCgojIENvbXB1dGUgdGhlIGRpc3RhbmNlIG1hdHJpeApjbHVzdGVyX2RhdGEgPC0gZGlzdChzY2FsZShzZWxlY3QoY3VzdG9tZXJzLCAtZXhjbHVkZSkpKQoKIyBVc2UgbWFwX2RibCB0byBydW4gbWFueSBtb2RlbHMgd2l0aCB2YXJ5aW5nIHZhbHVlIG9mIGsgKGNlbnRlcnMpCnRvdF93aXRoaW5zcyA8LSBtYXBfZGJsKDE6MTAsICBmdW5jdGlvbihrKXsKICBtb2RlbCA8LSBrbWVhbnMoeCA9IGNsdXN0ZXJfZGF0YSwgY2VudGVycyA9IGspCiAgbW9kZWwkdG90LndpdGhpbnNzCn0pCgojIEdlbmVyYXRlIGEgZGF0YSBmcmFtZSBjb250YWluaW5nIGJvdGggayBhbmQgdG90X3dpdGhpbnNzCmVsYm93X2RmIDwtIGRhdGEuZnJhbWUoCiAgayA9IDE6MTAsCiAgdG90X3dpdGhpbnNzID0gdG90X3dpdGhpbnNzCikKCgpnZ3Bsb3QoZWxib3dfZGYsIGFlcyh4ID0gaywgeSA9IHRvdF93aXRoaW5zcykpICsKICBnZW9tX2xpbmUoKSArCiAgZ2VvbV9wb2ludCgpICsKICBzY2FsZV94X2NvbnRpbnVvdXMoYnJlYWtzID0gMToxMCkgKwogIGxhYnMoeSA9ICJUb3RhbCB3aXRoaW4gc3VtIG9mIHNxdWFyZXMiLAogICAgICAgdGl0bGUgPSAiQ2hlY2sgZm9yIG9wdGltYWwgbnVtLiBvZiBzZWdtZW50cyAoRWxib3cgcGxvdCkiLAogICAgICAgc3VidGl0bGUgPSAiU3RvcCBhZGRpbmcgbmV3IHNlZ21lbnRzIHdoZW4gdGhlIGFkZGl0aW9uYWwgaW5mb3JtYXRpb24gaXMgbm90IHNpZ25pZmljYW50IiwKICAgICAgIHggPSAiTnVtYmVyIG9mIHNlZ21lbnRzIikKCmBgYAoKVGhlIGlkZWEgaGVyZSBpcyB0aGF0IHdlIHN0b3AgYWRkaW5nIG5ldyBzZWdtZW50cyB3aGVuIHRoZSBhZGRpdGlvbmFsIGluZm9ybWF0aW9uIAooaW5jcmVhc2Ugb24gdG90YWwgd2l0aGluIHN1bSBvZiBzcXVhcmVzKSBpcyBub3Qgc2lnbmlmaWNhbnQuIEluIHRoaXMgY2FzZSA0ICYgNSBjbHVzdGVycyBzZWVtcyBPSy4gCgpGaW5hbGx5IHdlIGNob29zZSB0byBwZXJmb3JtIHRoZSBzZWdtZW50YXRpb24gd2l0aCA1IHNlZ21lbnRzIGJlY2F1c2U6ICAKCmkpIGl0IGlzIGFtb25nIHRoZSBvcHRpbWFsIG51bWJlciBvZiBzZWdtZW50cyAmCmlpKSBzYXRpc2ZpZXMgb3VyIGJ1c2luZXNzIG5lZWRzLiAKCgojIyBCdWlsZCB0aGUgbW9kZWwgd2l0aCBrID0gNSAKCgpgYGB7cn0Kc2V0LnNlZWQoNDIpCgojIEJ1aWxkIGEgay1tZWFucyBtb2RlbCBmb3IgdGhlIGN1c3RvbWVycyB3aXRoIGEgayBvZiA1Cm1vZGVsX2N1c3RvbWVycyA8LSBrbWVhbnMoc2NhbGUoc2VsZWN0KGN1c3RvbWVycywgLWV4Y2x1ZGUpKSwgY2VudGVycyA9IDUpCgpgYGAKCgojIyBIZWF0bWFwIG9mIGNsdXN0ZXIgY2VudGVycyAKClRoaXMgaXMgYW4gZWFzeSB3YXkgdG8gY2hlY2sgdGhlIGRpZmZlcmVuY2VzICYgc2ltaWxhcml0aWVzIG9mIGFsbCBzZWdtZW50cy4gVGhlIApjZW50ZXIgb2YgdGhlIGNsdXN0ZXIgaXMgdGhlIGF2ZXJhZ2Ugb2YgYWxsIHBvaW50cyAoZWxlbWVudHMpIHRoYXQgYmVsb25nIHRvIHRoYXQKY2x1c3Rlci4gQWxsIHZhbHVlcyBhcmUgc2NhbGVkIAoKYGBge3IgZWNobz1GQUxTRSwgbWVzc2FnZT1GQUxTRSwgd2FybmluZz1GQUxTRSwgcGFnZWQucHJpbnQ9RkFMU0V9CgpkM2hlYXRtYXAoCiAgICAgIG1vZGVsX2N1c3RvbWVycyRjZW50ZXJzLCAKICAgICAgc2NhbGUgPSAiY29sdW1uIiwKICAgICAgZGVuZHJvZ3JhbSA9ICJib3RoIiwKICAgICAgQ29sdj1GQUxTRSwKICAgICAgY29sb3IgPSBzY2FsZXM6OmNvbF9xdWFudGlsZSgiR3JlZW5zIiwgTlVMTCwgNiksIAogICAgICBjZXhSb3cgPSAuNiwgCiAgICAgIHlheGlzX2ZvbnRfc2l6ZSA9IDEwKQoKYGBgCgpUaGUgbW9yZSBncmVlbiAtIHRoZSBoaWdoZXIgdGhlIHZhbHVlLiAKCi0JU2VnbWVudCAzIGNvbnRhaW5pbmcganVzdCA1IGN1c3RvbWVycy4gVGhlc2UgYXJlIG91ciAidG9wIiBjdXN0b21lcnMuIFRoZXkgdGVuZCB0byBnZW5lcmF0ZSB3YXkgbW9yZSByZXZlbnVlLCBoYXZlIGEgbG90IG9mIGNlcnRpZmljYXRpb25zLCBwdXJjaGFzZSBxdWl0ZSBhIGJpZyBwcm9wb3J0aW9uIG9mIG5ldyBwcm9kdWN0cyBhbmQgaGF2ZSBhIGhpZ2ggRFNPICAKCi0JU2VnbWVudCAyIGNvbnRhaW5zIDI3IGN1c3RvbWVycy4gVGhleSBhcmUgImNsb3NlIHRvIHRoZSB0b3AiIGN1c3RvbWVycyBhcyB0aGV5IHRlbmQgdG8gZ2VuZXJhdGUgaGlnaCByZXZlbnVlLCBtYWludGFpbiBhIGhpZ2ggbnVtYmVyIG9mIGNlcnRpZmljYXRpb25zLCBwdXJjaGFzZSBxdWl0ZSBhIGJpZyBwcm9wb3J0aW9uIG9mIG5ldyBwcm9kdWN0cyBhbmQgaGF2ZSBhIGhpZ2ggRFNPICAKCi0JU2VnbWVudCA0IGNvbnRhaW5zIDEwNiBjdXN0b21lcnMuIFRoZXkgYXJlIHRoZSAiYXZlcmFnZSIgY3VzdG9tZXJzIGFzIHRoZXkgdGVuZCB0byBnZW5lcmF0ZSBhdmVyYWdlIHJldmVudWVzLCBoYXZlIGEgc21hbGwgbnVtYmVyIG9mIGNlcnRpZmljYXRpb25zLCBwdXJjaGFzZSBhbiBhdmVyYWdlIHByb3BvcnRpb24gb2YgbmV3IHByb2R1Y3RzIGFuZCBoYXZlIGFuIGF2ZXJhZ2UgRFNPICAKCi0JU2VnbWVudCAxIGNvbnRhaW5zIDg3IGN1c3RvbWVycy4gVGhleSBhcmUgdGhlICJwcm9taXNpbmciIGN1c3RvbWVycyBhcyB0aGV5IHRlbmQgdG8gZ2VuZXJhdGUgYSByZWxhdGl2ZWx5IGxvdyByZXZlbnVlLCBoYXZlIGEgc21hbGwgbnVtYmVyIG9mIGNlcnRpZmljYXRpb25zLCBidXQgdGhleSBwdXJjaGFzZSBhIHZlcnkgaGlnaCBwcm9wb3J0aW9uIG9mIG5ldyBwcm9kdWN0cyBhbmQgaGF2ZSBhIHNtYWxsIERTTyAgCgotCVNlZ21lbnQgNSBjb250YWlucyAxNDMgY3VzdG9tZXJzLiBUaGV5IGFyZSB0aGUgInVuZGVyLXBlcmZvcm1pbmciIGN1c3RvbWVycyBhcyB0aGV5IHRlbmQgdG8gZ2VuZXJhdGUgYSB2ZXJ5IGxvdyByZXZlbnVlLCBoYXZlIGEgdmVyeSBzbWFsbCBudW1iZXIgb2YgY2VydGlmaWNhdGlvbnMsIHB1cmNoYXNlIGEgdmVyeSBsb3cgcHJvcG9ydGlvbiBvZiBuZXcgcHJvZHVjdHMgYW5kIGhhdmUgYW4gc21hbGwgRFNPICAKCgojIyBUYWJsZSBvZiB2YXJpYWJsZXMgCgoqKkJlbG93IHRoZXJlIGlzIGEgdGFibGUgd2l0aCBpbmZvcm1hdGlvbiBhYm91dCBhbGwgY2x1c3RlcnMgKHdpdGggYWxsIHZhcmlhYmxlcykqKgoKCmBgYHtyfQojIEV4dHJhY3QgdGhlIHZlY3RvciBvZiBjbHVzdGVyIGFzc2lnbm1lbnRzIGZyb20gdGhlIG1vZGVsCmNsdXN0X2N1c3RvbWVycyA8LSBtb2RlbF9jdXN0b21lcnMkY2x1c3RlcgoKIyBCdWlsZCB0aGUgc2VnbWVudF9jdXN0b21lcnMgZGF0YWZyYW1lCnNlZ21lbnRfY3VzdG9tZXJzIDwtIG11dGF0ZShzZWxlY3QoY3VzdG9tZXJzLCAtZXhjbHVkZSksIGNsdXN0ZXIgPSBjbHVzdF9jdXN0b21lcnMpCgojIENhbGN1bGF0ZSB0aGUgbWVhbiBmb3IgZWFjaCBjYXRlZ29yeQpzZWdtZW50X2N1c3RvbWVycyAlPiUgCiAgZ3JvdXBfYnkoY2x1c3RlcikgJT4lIAogIGFkZF90YWxseSgpICU+JSAKICBzdW1tYXJpc2VfZWFjaChmdW5zKHJvdW5kKG1lYW4oLiksMikpKSAlPiUgCiAgc2VsZWN0KDEsICJuIiwgZXZlcnl0aGluZygpKSAlPiUgCiAgYXJyYW5nZSgtbGFzdF95ZWFyX3JldmVudWUpICU+JSAKICBkYXRhdGFibGUoZmlsdGVyID0gJ3RvcCcsIG9wdGlvbnMgPSBsaXN0KHBhZ2VMZW5ndGggPSA1LCBhdXRvV2lkdGggPSBUUlVFLCBkb20gPSAncHQnKSkKCmBgYAoKCiMjIFBDQSAoUHJpbmNpcGFsIGNvbXBvbmVudHMgYW5hbHlzaXMpCgpJdCBpcyBhIGRpbWVuc2lvbmFsaXR5IHJlZHVjdGlvbiBhbGdvcml0aG0sIHRoYXQgYWxsb3dzIHlvdSB0byBzdW1tYXJpemUgdGhlCmluZm9ybWF0aW9uIGNvbnRlbnQgaW4gbGFyZ2UgZGF0YXNldHMgYnkgbWVhbnMgb2YgYSBzbWFsbGVyIHNldCBvZiBmZWF0dXJlcyB0aGF0IApjYW4gYmUgbW9yZSBlYXNpbHkgdmlzdWFsaXplZCBhbmQgYW5hbHl6ZWQuIEl0IHdpbGwgYXNzaXN0IHVzIGluIHNlZ21lbnRhdGlvbgp2aXN1YWxpemF0aW9uIChCaXBsb3QpLiAKCi0gSXQgd2lsbCBmaW5kIGxpbmVhciBjb21iaW5hdGlvbiBvZiB2YXJpYWJsZXMgdG8gY3JlYXRlIHByaW5jaXBhbCBjb21wb25lbnRzCi0gVGhlc2UgUHJpbmNpcGFsIGNvbXBvbmVudHMgY2FwdHVyZSB0aGUgbW9zdCB2YXJpYXRpb24gaW4gYSBkYXRhc2V0IGFuZCBhcmUgdW5jb3JyZWxhdGVkCgoKYGBge3J9CgpwY2FfY3VzdG9tZXJzIDwtIHByY29tcChzY2FsZShzZWxlY3QoY3VzdG9tZXJzLCAtZXhjbHVkZSkpKQpzdW1tYXJ5KHBjYV9jdXN0b21lcnMpCmBgYAoKCiMjIEJpcGxvdCAKClRoaXMgcGxvdCBzaG93cyBhbGwgdGhlIG9yaWdpbmFsIG9ic2VydmF0aW9ucyBwbG90dGVkIG9uIHRoZSBmaXJzdCAyIHByaW5jaXBhbCAKY29tcG9uZW50cyAod2hpY2ggY29udGFpbiBhbG1vc3QgNzUlIG9mIHRoZSBvcmlnaW5hbCBkYXRhc2V0IHZhcmlhbmNlKS4gSXQgYWxzbyAKc2hvd3MgdGhlIG9yaWdpbmFsIGZlYXR1cmVzIG1hcHBlZCBhcyB2ZWN0b3JzLgoKCmBgYHtyIGZpZy5oZWlnaHQ9NywgZmlnLndpZHRoPTEwfQoKICBnZ3Bsb3RseSgKICAgICAgICBhdXRvcGxvdChwY2FfY3VzdG9tZXJzLCBsb2FkaW5ncyA9IFRSVUUsIGxvYWRpbmdzLmxhYmVsID0gVFJVRSkgKwogICAgICAgICAgbGFicyh0aXRsZSA9ICJCaXBsb3Qgb2YgY3VzdG9tZXJzIGFuZCB2YXJpYWJsZXMiKSArCiAgICAgICAgICB0aGVtZV9maXZldGhpcnR5ZWlnaHQoKSkKCmBgYAoKSXQgc2hvd3MgdGhhdCB0aGVyZSBhcmUgMyBkaXN0aW5jdCBncm91cHMgb2YgdmFyaWFibGVzOgotIGFjdGl2ZV9xdWFydGVycyAmIG1lZGlhbl9kc28KLSBuZXdfcHJvZHVjdHNfcHJvcCAKLSBBbGwgdGhlIHJldmVudWUtcmVsYXRlZCB2YXJpYWJsZXMgCgoKIyMgIkJ1c2luZXNzIiBCaXBsb3QgCgpgYGB7ciBmaWcuaGVpZ2h0PTcsIGZpZy53aWR0aD0xMH0KCgpnZ3Bsb3RseSgKICAgICAgICAgIHBjYV9jdXN0b21lcnMkeCAlPiUKICAgICAgICAgIGFzLmRhdGEuZnJhbWUoKSAlPiUKICAgICAgICAgIG11dGF0ZShDTElFTlQgPSBjdXN0b21lcnMkY3VzdG9tZXIsCiAgICAgICAgICAgICAgICAgQ2x1c3RlciA9IGFzLmZhY3RvcihzZWdtZW50X2N1c3RvbWVycyRjbHVzdGVyKSwKICAgICAgICAgICAgICAgICByZXZlbnVlID0gc2VnbWVudF9jdXN0b21lcnMkbGFzdF95ZWFyX3JldmVudWUsCiAgICAgICAgICAgICAgICAgbmV3YnVzaW5lc3MgPSBzZWdtZW50X2N1c3RvbWVycyRuZXdfcHJvZHVjdHNfcHJvcCwKICAgICAgICAgICAgICAgICBjZXJ0aWZpY2F0aW9ucyA9IHNlZ21lbnRfY3VzdG9tZXJzJGNlcnRpZmljYXRpb25zKSAlPiUKICAgICAgICAgIHNlbGVjdChDTElFTlQsIENsdXN0ZXIsIFBDMSwgUEMyLCByZXZlbnVlLCBuZXdidXNpbmVzcywgY2VydGlmaWNhdGlvbnMpICU+JQogICAgICAgICAgZ2dwbG90KGFlcyhQQzEsIFBDMiwgY29sb3IgPSBDbHVzdGVyLCB0ZXh0ID0gcGFzdGUoQ0xJRU5ULCAiXG4gUmV2ZW51ZTogIiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICMgc2NhbGVzOjpkb2xsYXIocmV2ZW51ZSwgcHJlZml4ID0gIuKCrCIpLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHJldmVudWUsIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIlxuIE5ldyBQcm9kLiBSZXYuOiIsIG5ld2J1c2luZXNzLCAiJVxuQ2VydGlmaWNhdGlvbnM6IiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGNlcnRpZmljYXRpb25zLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgc2VwID0gIiIpICkpICsKICAgICAgICAgIAogICAgICAgICAgc3RhdF9lbGxpcHNlKGFlcyhsYWJlbCA9IENsdXN0ZXIsIGdyb3VwID0gQ2x1c3RlciksIHR5cGUgPSAibm9ybSIsIGxldmVsID0gMC43MCkgKwogICAgICAgICAgZ2VvbV9wb2ludCgpKwogICAgICAgICAgdGhlbWVfZml2ZXRoaXJ0eWVpZ2h0KCkgKwogICAgICAgICAgbGFicyh0aXRsZSA9ICJCdXNpbmVzcyBCaXBsb3Qgb2YgY3VzdG9tZXJzIiwKICAgICAgICAgICAgICAgeCA9ICIiLAogICAgICAgICAgICAgICB5ID0gIiIpICsKICAgICAgICAgIHNjYWxlX2NvbG9yX2Rpc2NyZXRlKG5hbWUgPSAiU2VnbWVudHMiKSArCiAgICAgICAgICB0aGVtZV9oYygpLAogICAgICAgIAogICAgICAgIHRvb2x0aXAgPSAidGV4dCIpCgoKYGBgCgpXZSBjYW4gc2VlIGhlcmUgaG93ICJ3ZWxsIiB0aGUgc2VnbWVudHMgYXJlIHNlcGFyYXRlZC4gRm9yIGV4YW1wbGU6ICAKLSBTZWdtZW50IDMgKCJ0b3AgY3VzdG9tZXJzIikgYXJlIHdlbGwgc2VwYXJhdGVkIGZyb20gdGhlIHJlc3QgIAotIFNlZ21lbnQgMiAoIkNsb3NlIHRvIHRvcCBjdXN0b21lcnMiKSBhcmUganVzdCBuZXh0IHRvIHRoZSB0b3AgY3VzdG9tZXJzLiAKLSBTZWdtZW50cyAxICYgNSBhcmUgb3ZlcmxhcHBpbmcuIAoKQWxtb3N0IGFsbCBzZWdtZW50cyBhcmUgY2xlYXJseSBkaXN0aW5ndWlzaGVkLgoKIyMgQ3VzdG9tZXIgc2VnbWVudGF0aW9uIHRhYmxlCgpgYGB7cn0KCmN1c3RvbWVycyAlPiUgCiAgbXV0YXRlKGNsdXN0ZXIgPSBjbHVzdF9jdXN0b21lcnMpICU+JSAKICBzZWxlY3QoY3VzdG9tZXIsIGFyZWEsIGNsdXN0ZXIsIGV2ZXJ5dGhpbmcoKSkgJT4lIAogIFZpZXcoKQoKYGBgCgpSZXBvcnRzIHRoZSBzZWdtZW50ICYgZGV0YWlscyBvZiBhbGwgY3VzdG9tZXJzLiAKCiMgQ09OQ0xVU0lPTlMKClRoZSBjaG9zZW4gIm9wdGltYWwiIG51bWJlciBvZiBjbHVzdGVycyBpcyA1LCB3aGljaCBpcyB3aXRoaW4gdGhlIGJ1c2luZXNzIG9iamVjdGl2ZXMKb2YgdGhlIGNvbXBhbnkuIEl0IGlzIGNydWNpYWwgdG8gd29yayB3aXRoIHRoZSBzdGFrZWhvbGRlcnMgd2hpbGUgcnVubmluZyB0aGUgYW5hbHlzaXMsIAppbiBvcmRlciB0byBwcm9kdWNlIGEgdXNlZnVsIG91dHB1dC4gCgoKIyMgU2VnbWVudHMgb3ZlcnZpZXcKClNlZ21lbnQgfCAjIGN1c3RvbWVycyB8IERlc2NyaXB0aW9uICAgICAgIHwgUGVyZm9ybWFuY2UgZXZhbHVhdGlvbiAgICAgICAgICAgICAKICAgMyAgICB8ICAgICAgICA1ICAgIHwgIlRvcCIgICAgICAgICAgICAgfCBWZXJ5IGhpZ2ggb24gYWxsIHZhcnMKICAgMiAgICB8ICAgICAgIDI3ICAgIHwgIkNsb3NlIHRvIHRvcCIgICAgfCBIaWdoIG9uIGFsbCB2YXJzCiAgIDQgICAgfCAgICAgIDEwNiAgICB8ICJBdmVyYWdlIiAgICAgICAgIHwgQXZlcmFnZSBvbiBhbGwgdmFycyAgCiAgIDEgICAgfCAgICAgICA4NyAgICB8ICJQcm9taXNpbmciICAgICAgIHwgVmVyeSBoaWdoIG5ldyBwcm9kdWN0cyByZXYuICYgbG93IG9uIHRoZSByZXN0CiAgIDUgICAgfCAgICAgIDE0MyAgICB8ICJVbmRlci1wZXJmb3JtZXJzInwgTG93IG9uIGFsbCB2YXJzCgojIyBTdWdlc3Rpb25zCgotIFdlIHNob3cgdGhhdCBhbG1vc3QgYWxsIHJldmVudWUtcmVsYXRlZCB2YXJpYWJsZXMgYXJlIGNvcnJlbGF0ZWQuIFdlIGNvdWxkIHJlbW92ZSBzb21lIG9yIG1vc3Qgb2YgdGhlc2UgdmFyaWFibGVzIGFzIHRoZXkgZG9uJ3QgcmVhbGx5IGhlbHAgdGhlIHNlZ21lbnRhdGlvbiBwcm9jZXNzLiAgCgotIEluIG9yZGVyIHRvIGltcHJvdmUgb3VyIHNlZ21lbnRhdGlvbiB3ZSBuZWVkIG1vcmUgZmVhdHVyZXMuIFdlIGNhbiBtZWV0IHdpdGggdGhlIHN0YWtlaG9sZGVycyBhbmQgd29yayBjbG9zZSB0byB0aGVtIHRvIGZpbmQgb3IgZ2VuZXJhdGUgc29tZSBtb3JlIGZlYXR1cmVzLiAgCgotIFdlIGNhbiB0cnkgbW9yZSBjbHVzdGVyaW5nIGFsZ29yaXRobXMsIGxpa2UgaGllcmFyY2hpY2FsIGNsdXN0ZXJpbmcsIERCU0NBTiBldGMuIAoKCgoKCg==